package study.biggestsequence;

public class Method4 {


    // 主函数，用于测试
    public static void main(String[] args) {
        double[] nums = {1.5, -12.3, 3.2, -5.5, 23.2, 3.2, -1.4, -12.2, 34.2, 5.4, -7.8,1.1,-4.9};
        Result result = maxSubArraySum(nums);
        System.out.println("Maximum Subarray Sum is " + result.maxSum);
        System.out.println("Start Index: " + result.startIndex);
        System.out.println("End Index: " + result.endIndex);
    }

    // 结果类，用于存储最大子数组和及其对应的区间
    static class Result {
        double maxSum;
        int startIndex;
        int endIndex;

        Result(double maxSum, int startIndex, int endIndex) {
            this.maxSum = maxSum;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }
    }

    // 分治法求解最大子数组和
    public static Result maxSubArraySum(double[] nums) {
        int n = nums.length;
        double[] leftMax = new double[n];
        double[] rightMax = new double[n];

        // 从左到右扫描
        double currentMax = nums[0];
        leftMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            leftMax[i] = Math.max(leftMax[i - 1], currentMax);
        }

        // 从右到左扫描
        currentMax = nums[n - 1];
        rightMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            rightMax[i] = Math.max(rightMax[i + 1], currentMax);
        }

        // 找出最大值并确定其对应的区间
        double maxSum = Double.MIN_VALUE;
        int startIndex = 0;
        int endIndex = 0;
        for (int i = 0; i < n - 1; i++) {
            double sum = leftMax[i] + rightMax[i + 1];
            if (sum > maxSum) {
                maxSum = sum;
                startIndex = i;
                endIndex = i + 1;
            }
        }

        return new Result(maxSum, startIndex, endIndex);
    }
}
